package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1039 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 这题其实我有思路，不过想的和标准答案有区别，划分子问题方式不同
     * 标准答案参考：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/solution/qu-jian-dong-tai-gui-hua-4ms-by-njyang-yang-yang/
     * @return:
     */
    class Solution {
        public int minScoreTriangulation(int[] values) {
            int n = values.length;
            int[][] dp = new int[n][n];
            for (int i = n - 3; i >= 0; i--) {
                for (int j = i + 2; j < n; j++) {
                    for (int m = i + 1; m < j; m++) {
                        if (dp[i][j] == 0)
                            dp[i][j] = values[i] * values[j] * values[m] + dp[i][m] + dp[m][j];
                        else
                            dp[i][j] = Math.min(dp[i][j], values[i] * values[j] * values[m] + dp[i][m] + dp[m][j]);
                    }
                }
            }
            return dp[0][n - 1];

        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC1039 an = new LC1039();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
